


# 198. 打家劫舍

def rob(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    dp = [None] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[1],dp[0])
    for i in range(2, len(nums)):
        dp[i] = max(dp[i - 2]+nums[i], dp[i - 1])
    return max(dp)


if __name__ == "__main__":
    nums = [2,7,9,3,1]
    print(rob(nums))